package mine.code.day.year2021.month08;

import org.junit.Test;

import java.util.Arrays;

/**
 * 假设有从 1 到 N 的N个整数，如果从这N个数字中成功构造出一个数组，使得数组的第 i位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
 * <p>
 * 第i位的数字能被i整除
 * i 能被第 i 位上的数字整除
 * 现在给定一个整数 N，请问可以构造多少个优美的排列？
 *
 * @author caijinnan
 */
public class Day16_优美的排列 {


    @Test
    public void run() {
        System.out.println(countArrangement(4));
//        for (int i = 1; i <= 8; i++) {
//            System.out.println(countArrangementTest(i));
//        }
    }

    public int countArrangement(int n) {
        int[] numArr = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};
        int[][] arrangement = new int[n][];
        for (int i = 1; i <= n; i++) {
            int needLength = 0;
            int[] indexArr = new int[n];
            for (int j = 1; j <= n; j++) {
                if (i % j == 0 || j % i == 0) {
                    indexArr[needLength] = numArr[j - 1];
                    needLength++;
                }
            }
            arrangement[i - 1] = Arrays.copyOf(indexArr, needLength);
        }
        return getSum(arrangement, arrangement.length, 0,  0, 0);
    }

    public int getSum(int[][] array, int length, int index, int numTemp, int sum) {
        if (index == length) {
            sum++;
            return sum;
        }

        for (int j = 0; j < array[index].length; j++) {
            //数组中的每一位遍历一次
            int tempNum = array[index][j];
            if ((numTemp ^ tempNum) <= numTemp) {
                continue;
            }
            sum = getSum(array, length, index + 1, numTemp ^ tempNum, sum);
        }
        return sum;
    }


}
